{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Course Schedule II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #课程表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现在你总共有 <code>numCourses</code> 门课需要选，记为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>numCourses - 1</code>。给你一个数组&nbsp;<code>prerequisites</code> ，其中 <code>prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> ，表示在选修课程 <code>a<sub>i</sub></code> 前 <strong>必须</strong> 先选修&nbsp;<code>b<sub>i</sub></code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，想要学习课程 <code>0</code> ，你需要先完成课程&nbsp;<code>1</code> ，我们用一个匹配来表示：<code>[0,1]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 <strong>任意一种</strong> 就可以了。如果不可能完成所有课程，返回 <strong>一个空数组</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numCourses = 2, prerequisites = [[1,0]]\n",
    "<strong>输出：</strong>[0,1]\n",
    "<strong>解释：</strong>总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 <code>[0,1] 。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]\n",
    "<strong>输出：</strong>[0,2,1,3]\n",
    "<strong>解释：</strong>总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。\n",
    "因此，一个正确的课程顺序是&nbsp;<code>[0,1,2,3]</code> 。另一个正确的排序是&nbsp;<code>[0,2,1,3]</code> 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numCourses = 1, prerequisites = []\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<strong>提示：</strong>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= numCourses &lt;= 2000</code></li>\n",
    "\t<li><code>0 &lt;= prerequisites.length &lt;= numCourses * (numCourses - 1)</code></li>\n",
    "\t<li><code>prerequisites[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; numCourses</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>所有<code>[a<sub>i</sub>, b<sub>i</sub>]</code> <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [course-schedule-ii](https://leetcode.cn/problems/course-schedule-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [course-schedule-ii](https://leetcode.cn/problems/course-schedule-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[[1,0]]', '4\\n[[1,0],[2,0],[3,1],[3,2]]', '1\\n[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = {v:[] for v in range(numCourses)}\n",
    "        visited = set()\n",
    "        cycle = set()\n",
    "        result = []\n",
    "\n",
    "        for course, pre in prerequisites:\n",
    "            graph[course].append(pre)\n",
    "\n",
    "        def dfs(course):\n",
    "            if course in cycle:\n",
    "                return False\n",
    "            if course in visited:\n",
    "                return True\n",
    "            \n",
    "            cycle.add(course)\n",
    "\n",
    "            for dep in graph[course]:\n",
    "                if dfs(dep) == False:\n",
    "                    return False\n",
    "            \n",
    "            cycle.remove(course)\n",
    "            visited.add(course)\n",
    "            result.append(course)\n",
    "\n",
    "        \n",
    "        for course in graph:\n",
    "            if dfs(course) == False:\n",
    "                return []\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # if not numCourses: return []\n",
    "        res, nextcourse, indegree = [], {}, [0] * numCourses\n",
    "        # 构建字典，键为课程，值为上完编号为键的课可以上的下一节课\n",
    "        for item in prerequisites:\n",
    "            if item[1] not in nextcourse:\n",
    "                nextcourse[item[1]] = [item[0]]\n",
    "            else:\n",
    "                nextcourse[item[1]].append(item[0])\n",
    "            # 统计每一个课程的入度\n",
    "            indegree[item[0]] += 1\n",
    "        # 统计入度为0的课程\n",
    "        queue = deque()\n",
    "        for i in range(numCourses):\n",
    "            if not indegree[i]: queue.append(i)\n",
    "        # 只要有入度为0的课程就继续循环\n",
    "        while queue:\n",
    "            c = queue.popleft()\n",
    "            res.append(c)\n",
    "            # 下一次将要上的课程\n",
    "            for _next in nextcourse.get(c, []):\n",
    "                # 当前课程已经上了，下一节课入度减一\n",
    "                indegree[_next] -= 1\n",
    "                # 将新产生的入度为0的课程添加到队列中\n",
    "                if not indegree[_next]: queue.append(_next)\n",
    "        for item in indegree:\n",
    "            if item: return []\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, n, pre):\n",
    "        res=[]\n",
    "        p=dict((i,0) for i in range(n))\n",
    "        o=dict((i,list()) for i in range(n))\n",
    "        for i in pre:\n",
    "            p[i[0]]+=1\n",
    "            o[i[1]].append(i[0])\n",
    "        queue=[i for i in p.keys() if p[i]==0]\n",
    "        while queue!=[]:\n",
    "            t=queue.pop(0)\n",
    "            res.append(t)\n",
    "            for i in o[t]:\n",
    "                p[i]-=1\n",
    "                if p[i]==0:\n",
    "                    queue.append(i)\n",
    "        return res if len(res)==n else []\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        self.graph=[[] for _ in range(numCourses)]\n",
    "        self.indegree=[0 for _ in range(numCourses)]\n",
    "        for i in prerequisites:\n",
    "            self.indegree[i[0]]+=1\n",
    "            self.graph[i[1]].append(i[0])\n",
    "        r=[]\n",
    "        begin=[i for i,j in enumerate(self.indegree) if j == 0]\n",
    "        while begin:\n",
    "            temp=begin.pop()\n",
    "            r.append(temp)\n",
    "            for to in self.graph[temp]:\n",
    "                self.indegree[to]-=1\n",
    "                if self.indegree[to]==0:\n",
    "                    begin.append(to)\n",
    "        if len(r)==numCourses:\n",
    "            return r\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class CustomNode:\n",
    "    def __init__(self, index):\n",
    "        self.beDepend = set()\n",
    "        self.dependCount = 0\n",
    "        self.val = index\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        nodeList = []\n",
    "        for i in range(numCourses):\n",
    "            nodeList.append(CustomNode(i))\n",
    "\n",
    "        for dependList in prerequisites:\n",
    "            curNode = nodeList[dependList[0]]\n",
    "            for index in range(1, len(dependList)):\n",
    "                curNode.dependCount += 1\n",
    "                dependNode = nodeList[dependList[index]]\n",
    "                dependNode.beDepend.add(curNode)\n",
    "\n",
    "\n",
    "        queue = []\n",
    "        for node in nodeList:\n",
    "            if node.dependCount == 0:\n",
    "                queue.append(node)\n",
    "\n",
    "        resultList = []\n",
    "        while len(queue) != 0:\n",
    "            curNode = queue.pop(0)\n",
    "            resultList.append(curNode.val)\n",
    "            for node in curNode.beDepend:\n",
    "                node.dependCount -= 1\n",
    "                if node.dependCount == 0:\n",
    "                    queue.append(node)\n",
    "\n",
    "        if len(resultList) != numCourses:\n",
    "            return []\n",
    "\n",
    "        return resultList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        graph = collections.defaultdict(list)\n",
    "        \n",
    "        for u, v in prerequisites:\n",
    "            graph[u].append(v)\n",
    "        path = []\n",
    "        visited = [0] * numCourses\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if not self.dfs(graph, path, i, visited):\n",
    "                return []\n",
    "        return path\n",
    "    \n",
    "    def dfs(self, graph, path, i, visited):\n",
    "        if visited[i] == 1:\n",
    "            return False\n",
    "        if visited[i] == 2:\n",
    "            return True\n",
    "        \n",
    "        visited[i] = 1\n",
    "        for j in graph[i]:\n",
    "            if not self.dfs(graph, path, j, visited):\n",
    "                return False\n",
    "        visited[i] = 2\n",
    "        path.append(i)\n",
    "        return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        not_ = {i:set() for i in range(numCourses)}\n",
    "        ok_ = collections.defaultdict(set)\n",
    "        \n",
    "        for i,j in prerequisites:\n",
    "            not_[i].add(j)\n",
    "            ok_[j].add(i)\n",
    "            \n",
    "        queue = collections.deque([i for i in not_ if not not_[i]])\n",
    "        res = []\n",
    "        while queue:\n",
    "            i = queue.popleft()\n",
    "            res.append(i)\n",
    "\n",
    "            for j in ok_[i]:\n",
    "                not_[j].remove(i)\n",
    "                \n",
    "                if not not_[j]:\n",
    "                    queue.append(j)\n",
    "            not_.pop(i)\n",
    "        return res if len(not_)==0 else []\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "#         not_ = {i:set() for i in range(numCourses)}\n",
    "#         ok_ = collections.defaultdict(set)\n",
    "        \n",
    "#         for i,j in prerequisites:\n",
    "#             not_[i].add(j)\n",
    "#             ok_[j].add(i)\n",
    "#         res = []\n",
    "#         queue = collections.deque([i for i in not_ if not not_[i]])\n",
    "        \n",
    "#         while queue:\n",
    "#             i = queue.popleft()\n",
    "#             res.append(i)\n",
    "            \n",
    "#             for j in ok_[i]:\n",
    "#                 not_[j].remove(i)\n",
    "#                 if not not_[j]:\n",
    "#                     queue.append(j)\n",
    "#             not_.pop(i)\n",
    "#         return res if not not_ else []\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 210. 课程表 II\n",
    "# 现在你总共有 n 门课需要选，记为 0 到 n-1。\n",
    "# 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]\n",
    "# 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。\n",
    "# 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "    def findOrder(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int 课程门数\n",
    "        :type prerequisites: List[List[int]] 课程与课程之间的关系\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # 课程的长度\n",
    "        clen = len(prerequisites)\n",
    "        if clen == 0:\n",
    "            # 没有课程，当然可以完成课程的学习\n",
    "            return [i for i in range(numCourses)]\n",
    "\n",
    "        # 逆邻接表\n",
    "        inverse_adj = [set() for _ in range(numCourses)]\n",
    "        # 想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]\n",
    "        # 1 -> 0，这里要注意：不要弄反了\n",
    "        for second, first in prerequisites:\n",
    "            inverse_adj[second].add(first)\n",
    "\n",
    "        visited = [0 for _ in range(numCourses)]\n",
    "        # print(\"in_degrees\", in_degrees)\n",
    "        # 首先遍历一遍，把所有入度为 0 的结点加入队列\n",
    "\n",
    "        res = []\n",
    "        for i in range(numCourses):\n",
    "            if self.__dfs(i,inverse_adj, visited, res):\n",
    "                return []\n",
    "        return res\n",
    "\n",
    "    def __dfs(self, vertex, inverse_adj, visited, res):\n",
    "        \"\"\"\n",
    "        注意：这个递归方法的返回值是返回是否有环\n",
    "        :param vertex: 结点的索引\n",
    "        :param inverse_adj: 逆邻接表，记录的是当前结点的前驱结点的集合\n",
    "        :param visited: 记录了结点是否被访问过，2 表示当前正在 DFS 这个结点\n",
    "        :return: 是否有环\n",
    "        \"\"\"\n",
    "        # 2 表示这个结点正在访问\n",
    "        if visited[vertex] == 2:\n",
    "            # DFS 的时候如果遇到一样的结点，就表示图中有环，课程任务便不能完成\n",
    "            return True\n",
    "        if visited[vertex] == 1:\n",
    "            return False\n",
    "        # 表示正在访问这个结点\n",
    "        visited[vertex] = 2\n",
    "        # 递归访问前驱结点\n",
    "        for precursor in inverse_adj[vertex]:\n",
    "            # 如果没有环，就返回 False，\n",
    "            # 执行以后，逆拓扑序列就存在 res 中\n",
    "            if self.__dfs(precursor, inverse_adj, visited, res):\n",
    "                return True\n",
    "        \n",
    "        # 能走到这里，说明所有的前驱结点都访问完了，所以可以输出了\n",
    "        # 并且将这个结点状态置为 1\n",
    "        visited[vertex] = 1\n",
    "        res.append(vertex)\n",
    "        # 最后不要忘记返回 False 表示无环\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, n, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 方法二：dfs\n",
    "        graph = {}\n",
    "        for x, y in prerequisites:\n",
    "            if y not in graph:\n",
    "                graph[y] = []\n",
    "            graph[y].append(x)\n",
    "        ans = []\n",
    "        memo = set()\n",
    "        self.possible = True\n",
    "        def dfs(start, visited):\n",
    "            if start in visited:\n",
    "                self.possible = False\n",
    "                return\n",
    "            visited.add(start)\n",
    "            if start in graph:\n",
    "                for nextvertex in graph[start]:\n",
    "                    if nextvertex not in memo:\n",
    "                        dfs(nextvertex, visited)\n",
    "            visited.discard(start)\n",
    "            memo.add(start)\n",
    "            ans.append(start)\n",
    "        for i in range(n):\n",
    "            if i not in memo:\n",
    "                dfs(i, set())\n",
    "        ans.reverse()\n",
    "        if self.possible:\n",
    "            return ans\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        E=defaultdict(list)\n",
    "        for [p,q] in prerequisites:\n",
    "            E[q].append(p)\n",
    "        #初始化顶点属性\n",
    "        color=['white']*numCourses\n",
    "        time={}\n",
    "        self.time=0\n",
    "        self.re=True\n",
    "        def dfs(node):\n",
    "            self.time+=1\n",
    "            color[node]='gray'\n",
    "            for u in E[node]:\n",
    "                if color[u]=='gray':\n",
    "                    self.re=False\n",
    "                elif color[u]=='white':\n",
    "                    dfs(u)\n",
    "            self.time+=1\n",
    "            color[node]='black'\n",
    "            time[node]=self.time\n",
    "        for node in range(numCourses):\n",
    "            if self.re and color[node]=='white':\n",
    "                dfs(node)\n",
    "            elif self.re==False:\n",
    "                return []\n",
    "        re=sorted(time.items(),reverse=True,key=lambda x:x[1])\n",
    "        return [t[0] for t in re]\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "    def findOrder(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int 课程门数\n",
    "        :type prerequisites: List[List[int]] 课程与课程之间的关系\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # 课程的长度\n",
    "        clen = len(prerequisites)\n",
    "        if clen == 0:\n",
    "            # 没有课程，当然可以完成课程的学习\n",
    "            return [i for i in range(numCourses)]\n",
    "\n",
    "        # 邻接表\n",
    "        adj = [set() for _ in range(numCourses)]\n",
    "        # 想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]\n",
    "        # 1 -> 0，这里要注意：不要弄反了\n",
    "        for second, first in prerequisites:\n",
    "            adj[second].add(first)\n",
    "\n",
    "        visited = [0 for _ in range(numCourses)]\n",
    "        # print(\"in_degrees\", in_degrees)\n",
    "        # 首先遍历一遍，把所有入度为 0 的结点加入队列\n",
    "\n",
    "        res = []\n",
    "        for i in range(numCourses):\n",
    "            if self.__dfs(i, adj, visited, res):\n",
    "                return []\n",
    "        return res\n",
    "\n",
    "    def __dfs(self, vertex, adj, visited, res):\n",
    "\n",
    "        if visited[vertex] == 2:\n",
    "            return True\n",
    "        if visited[vertex] == 1:\n",
    "            return False\n",
    "        # 表示正在访问这个结点\n",
    "        visited[vertex] = 2\n",
    "        # 递归访问前驱结点\n",
    "        for precursor in adj[vertex]:\n",
    "            # 如果没有环，就返回 False，\n",
    "            # 执行以后，逆拓扑序列就存在 res 中\n",
    "            if self.__dfs(precursor, adj, visited, res):\n",
    "                return True\n",
    "        # 能走到这里，说明所有的前驱结点都访问完了，所以可以输出了\n",
    "        # 并且将这个结点状态置为 1\n",
    "        visited[vertex] = 1\n",
    "        res.append(vertex)\n",
    "        print(vertex)\n",
    "        # 最后不要忘记返回 False 表示无环\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: 'int', prerequisites: 'List[List[int]]') -> 'List[int]':\n",
    "        adj = [[]]*numCourses\n",
    "        for i in range(numCourses):\n",
    "            adj[i] = []\n",
    "        inDegrees = [0]*numCourses\n",
    "        for edge in prerequisites:\n",
    "            inDegrees[edge[0]] += 1\n",
    "            adj[edge[1]].append(edge[0])\n",
    "        q = [-1]*numCourses\n",
    "        front = 0\n",
    "        tail = 0\n",
    "        for i in range(numCourses):\n",
    "            if inDegrees[i] == 0:\n",
    "                q[tail] = i\n",
    "                tail += 1\n",
    "        order = []\n",
    "        while front < tail:\n",
    "            top = q[front]\n",
    "            order.append(top)\n",
    "            front+=1\n",
    "            for n in adj[top]:\n",
    "                inDegrees[n]-=1\n",
    "                if inDegrees[n] == 0:\n",
    "                    q[tail] = n\n",
    "                    tail+=1\n",
    "        if any(inDegrees):\n",
    "            return []\n",
    "        return order\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: 'int', prerequisites: 'List[List[int]]') -> 'List[int]':\n",
    "        gragh=[[] for i in range(numCourses)]\n",
    "        pre = [0] * numCourses# 记录每个节点有多少个前驱结点\n",
    "        # 这样前驱结点，就变成了后继节点\n",
    "        for x,y in prerequisites:\n",
    "            pre[x]+=1\n",
    "            gragh[y].append(x)\n",
    "            \n",
    "        def bfs(candidates,res):\n",
    "            queen=candidates\n",
    "            path=candidates\n",
    "            \n",
    "            \n",
    "            \n",
    "            while(queen):\n",
    "                # print(queen)\n",
    "                # print(path)\n",
    "                new_layer=[]\n",
    "                new_path=[]\n",
    "                \n",
    "                for i in range(len(queen)):\n",
    "                    for node in gragh[queen[i]]:\n",
    "                        pre[node]-=1\n",
    "                        if pre[node]==0:\n",
    "                            new_layer.append(node)\n",
    "                new_path=path+new_layer\n",
    "                if len(new_path)==numCourses:\n",
    "                    # new_layer.pop()\n",
    "                    res.append(new_path)\n",
    "                \n",
    "                            \n",
    "                queen=new_layer                 \n",
    "                path=new_path\n",
    "                \n",
    "        \n",
    "        res=[]\n",
    "        can=[x for x in range(numCourses) if pre[x]==0]\n",
    "        print(can,gragh)\n",
    "        bfs(can,res)\n",
    "        # print(res)\n",
    "        if res==[]:\n",
    "            return []\n",
    "        else:\n",
    "            return res[0]\n",
    "        \n",
    "        \n",
    "#         # 可以，但会超时\n",
    "#         gragh=[[] for i in range(numCourses)]\n",
    "        \n",
    "        \n",
    "        \n",
    "#         for x,y in prerequisites:\n",
    "#             gragh[x].append(y)\n",
    "\n",
    "#         candidates=[i for i in range(numCourses)]# 直接=赋不上值\n",
    "        \n",
    "#         print(gragh)\n",
    "#         def dfs(candidates,path,res):\n",
    "#             if len(candidates)==0:\n",
    "#                 res.append(path[::-1])\n",
    "#                 return\n",
    "\n",
    "#             for i in range(len(candidates)):\n",
    "#                 candidates_in=candidates[:]\n",
    "#                 path_in=candidates_in.pop(i)\n",
    "                \n",
    "#                 flag=True\n",
    "#                 for x in gragh[candidates[i]]:\n",
    "#                     if x not in candidates_in:\n",
    "#                         flag=False\n",
    "#                 if flag:\n",
    "#                     dfs(candidates_in,path+[path_in],res)\n",
    "            \n",
    "#         res=[]\n",
    "#         dfs(candidates,[],res)\n",
    "#         if res==[]:\n",
    "#             return res\n",
    "#         else:\n",
    "#             return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        a = [0 for i in range(numCourses)]\n",
    "        b = [[] for i in range(numCourses)]\n",
    "        queue = []\n",
    "        for cur, pre in prerequisites:\n",
    "            a[cur] += 1\n",
    "            b[pre].append(cur)\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if not a[i]: \n",
    "            \tqueue.append(i)\n",
    "      \n",
    "\n",
    "        while queue:\n",
    "            clss = queue.pop()\n",
    "            res.append(clss)\n",
    "            for i in b[clss]:\n",
    "                a[i] -= 1\n",
    "                if not a[i]:\n",
    "                    queue.append(i)\n",
    "        return res if len(res) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        if len(prerequisites)<=0:\n",
    "            # no requirement\n",
    "            return list(range(numCourses))\n",
    "        \n",
    "        # edge\n",
    "        from collections import defaultdict\n",
    "        edge = defaultdict(list)\n",
    "        in_e = [0]*numCourses\n",
    "        for cur, req in prerequisites: \n",
    "            edge[req].append(cur) # store 出度, 用于之后减去的\n",
    "            in_e[cur]+=1\n",
    "        # print(edge)\n",
    "\n",
    "        # BFS\n",
    "        #       add input 0 edge. and then remove all edge linked to them.\n",
    "        bfs = [x for x in range(numCourses) if not in_e[x]]\n",
    "        result = [] \n",
    "        while bfs:\n",
    "            \n",
    "            cur = bfs.pop()\n",
    "            result.append(cur)\n",
    "            for node in edge[cur]:\n",
    "                in_e[node] -= 1\n",
    "                if in_e[node]==0:\n",
    "                    # 只从新连的边里一个一个加\n",
    "                    bfs.insert(0, node) \n",
    "            \n",
    "        if len(result)<numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return result\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # edges = collections.defaultdict(list)\n",
    "        # visited = [0] * numCourses\n",
    "        # self.valid = True\n",
    "        # res = []\n",
    "        \n",
    "        # for edge_ in prerequisites:\n",
    "        #     edges[edge_[1]].append(edge_[0])\n",
    "        \n",
    "        # def dfs(node):\n",
    "        #     visited[node] = 1\n",
    "        #     for nei_node in edges[node]:\n",
    "        #         if visited[nei_node] == 0:\n",
    "        #             dfs(nei_node)\n",
    "        #             if self.valid == False:\n",
    "        #                 return \n",
    "        #         elif visited[nei_node] == 1:\n",
    "        #             self.valid = False\n",
    "        #             return\n",
    "        #     visited[node] = 2\n",
    "        #     res.append(node)\n",
    "        \n",
    "        # for i in range(numCourses):\n",
    "        #     if self.valid and visited[i] == 0:\n",
    "        #         dfs(i)\n",
    "\n",
    "        # if self.valid:\n",
    "        #     res.reverse()\n",
    "        #     return res\n",
    "        # else:\n",
    "        #     return []\n",
    "\n",
    "        edges = collections.defaultdict(list)\n",
    "        in_degree = [0] * numCourses\n",
    "        self.valid = True\n",
    "        res = []\n",
    "        \n",
    "        for edge_ in prerequisites:\n",
    "            edges[edge_[1]].append(edge_[0])\n",
    "            in_degree[edge_[0]] += 1\n",
    "        \n",
    "        q = collections.deque([ u  for u in range(numCourses) if in_degree[u] == 0])\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            res.append(u)\n",
    "            for v in edges[u]:\n",
    "                in_degree[v] -= 1\n",
    "                if in_degree[v] == 0:\n",
    "                    q.append(v)\n",
    "        if len(res) == numCourses:\n",
    "            return res\n",
    "        else:\n",
    "            return []\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self, prerequisites, graph, degree):\n",
    "        for x in prerequisites:\n",
    "            degree[x[0]] = 1 if x[0] not in degree else degree[x[0]]+1\n",
    "            if x[1] not in degree:\n",
    "                degree[x[1]] = 0\n",
    "            if x[1] in graph:\n",
    "                graph[x[1]].append(x[0])\n",
    "            elif x[1] not in graph:\n",
    "                graph[x[1]] = [x[0]]\n",
    "\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = {}\n",
    "        degree = {}\n",
    "        zero_nodes = []\n",
    "        for i in range(numCourses):\n",
    "            graph[i] = []\n",
    "            degree[i] = 0\n",
    "        self.build_graph(prerequisites, graph, degree)\n",
    "        for x in degree:\n",
    "            if degree[x] == 0:\n",
    "                zero_nodes.append(x)\n",
    "        stack = []\n",
    "\n",
    "        def order(degree, graph, zero_nodes):\n",
    "            first_node = -1\n",
    "            while len(zero_nodes) != 0 and zero_nodes[0] != first_node:\n",
    "                first_node = zero_nodes[0]\n",
    "                x = zero_nodes[0]\n",
    "                stack.append(x)\n",
    "                if x in graph:\n",
    "                    for y in graph[x]:\n",
    "                        degree[y] = degree[y] - 1\n",
    "                        if degree[y] == 0:\n",
    "                            zero_nodes.append(y)\n",
    "                    zero_nodes.pop(0)\n",
    "                    graph[x] = []\n",
    "\n",
    "        order(degree, graph, zero_nodes)\n",
    "        if len(stack) != numCourses:\n",
    "            return []\n",
    "        return stack\n",
    "\n",
    "\n",
    "s = Solution()\n",
    "num = 4\n",
    "pre = [[1,0],[2,0],[3,1],[3,2]]\n",
    "print(s.findOrder(num, pre))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 存储有向图\n",
    "        edges = collections.defaultdict(list)\n",
    "        # 存储每个节点的入度\n",
    "        indeg = [0] * numCourses\n",
    "        # 存储答案\n",
    "        result = list()\n",
    "\n",
    "        for info in prerequisites:\n",
    "            edges[info[1]].append(info[0])\n",
    "            indeg[info[0]] += 1\n",
    "\n",
    "        # 将所有入度为 0 的节点放入队列中\n",
    "        q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])\n",
    "\n",
    "        while q:\n",
    "            # 从队首取出一个节点\n",
    "            u = q.popleft()\n",
    "            # 放入答案中\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                # 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if len(result) != numCourses:\n",
    "            result = list()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "\n",
    "#         def dfs(idx):\n",
    "#             visited[idx] = 1\n",
    "#             for r in require[idx]:\n",
    "#                 if visited[r] == 1:\n",
    "#                     return False\n",
    "#                 elif visited[r] == 0:\n",
    "#                     if not dfs(r):\n",
    "#                         return False\n",
    "#             visited[idx] = 2\n",
    "#             seq.append(idx)\n",
    "#             return True\n",
    "\n",
    "#         require = [[] for _ in range(numCourses)]\n",
    "#         for p in prerequisites:\n",
    "#             require[p[0]].append(p[1])\n",
    "\n",
    "#         visited = [0] * numCourses    # 0表示未处理，1表示处理中，2表示已处理\n",
    "#         seq = []\n",
    "#         for i in range(numCourses):\n",
    "#             if visited[i] == 2:\n",
    "#                 continue\n",
    "            \n",
    "#             # visited[i] == 0\n",
    "#             if not dfs(i):\n",
    "#                 return []\n",
    "#         return seq\n",
    "\n",
    "\n",
    "# 拓扑排序的方法\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        require = [[] for _ in range(numCourses)]\n",
    "        indegree = [0] * numCourses\n",
    "        for p in prerequisites:\n",
    "            require[p[1]].append(p[0])\n",
    "            indegree[p[0]] += 1\n",
    "\n",
    "        queue = []\n",
    "        for i in range(numCourses):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        order = []\n",
    "        while queue:\n",
    "            u = queue[0]\n",
    "            queue = queue[1:]\n",
    "            order.append(u)\n",
    "            for v in require[u]:\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    queue.append(v)\n",
    "        \n",
    "        return order if sum(indegree) == 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def build_graph(edges):\n",
    "    graph_in = collections.defaultdict(set)\n",
    "    graph_out = collections.defaultdict(set)\n",
    "    for edge in edges:\n",
    "        graph_in[edge[1]].add(edge[0])\n",
    "        graph_out[edge[0]].add(edge[1])\n",
    "    return graph_out, graph_in\n",
    "\n",
    "\n",
    "def topo(graph_in, graph_out):\n",
    "    count = {}  # 节点入射边统计\n",
    "    queue = []  # 当前入射边为0的节点列表\n",
    "\n",
    "    # 统计所有节点的入射边\n",
    "    for node in graph_in:\n",
    "        count[node] = len(graph_in[node])\n",
    "    for node in graph_out:\n",
    "        if node not in count:\n",
    "            count[node] = 0\n",
    "            queue.append(node)\n",
    "\n",
    "    # 拓扑排序\n",
    "    order = []\n",
    "    while queue:\n",
    "        node = queue.pop()\n",
    "        order.append(node)\n",
    "        for next in graph_out[node]:\n",
    "            count[next] -= 1\n",
    "            if count[next] == 0:\n",
    "                queue.append(next)\n",
    "\n",
    "    return order\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 生成有向图中边的邻接列表结构\n",
    "        graph_in, graph_out = build_graph(prerequisites)\n",
    "\n",
    "        # 拓扑排序\n",
    "        order = topo(graph_in, graph_out)\n",
    "        order_set = set(order)\n",
    "\n",
    "        for node in graph_in:\n",
    "            if node not in order:\n",
    "                return []\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            if i not in order_set:\n",
    "                order.append(i)\n",
    "\n",
    "        return order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 入度表\n",
    "        in_degree = [0] * numCourses\n",
    "        # 前驱表\n",
    "        front = [[] for _ in range(numCourses)]\n",
    "        for cur, prev in prerequisites:\n",
    "            front[cur].append(prev)\n",
    "            in_degree[prev] += 1\n",
    "\n",
    "        result = []\n",
    "        stack = [i for i, d in enumerate(in_degree) if d == 0]\n",
    "        # count = 0\n",
    "        while stack:\n",
    "            v = stack.pop()\n",
    "            result.append(v)\n",
    "            # count += 1\n",
    "            for prev in front[v]:\n",
    "                in_degree[prev] -= 1\n",
    "                if in_degree[prev] == 0:\n",
    "                    stack.append(prev)\n",
    "        result.reverse()\n",
    "        return result if len(result) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # res 为返回值，有环返回空，没有环返回具体的排序\n",
    "        res = []\n",
    "        # 字典记录图，key为被依赖的节点，value为一个依赖key节点的节点数组\n",
    "        dict = collections.defaultdict(list)\n",
    "        # 存储每个节点的入节点，也就是一个节点有几个入边，就是有几个依赖，没有依赖就可以放到结果数组中\n",
    "        vlen = [0]*numCourses\n",
    "        # 队列，用于遍历的节点\n",
    "        qq = collections.deque()\n",
    "        # 构建图\n",
    "        for info in prerequisites:\n",
    "            dict[info[1]].append(info[0])\n",
    "            vlen[info[0]] += 1\n",
    "        # 把入边是0的写入到qq,从他们开始循环\n",
    "        for i in range(numCourses):\n",
    "            if vlen[i] == 0:\n",
    "                qq.append(i)\n",
    "\n",
    "        # 广度搜索\n",
    "        while qq:\n",
    "            cur = qq.popleft()\n",
    "            res.append(cur)\n",
    "            for i in dict[cur]:\n",
    "                if vlen[i] >= 1:\n",
    "                    vlen[i] -= 1\n",
    "                if vlen[i] == 0:\n",
    "                    qq.append(i)\n",
    "        if len(res) !=  numCourses:\n",
    "            return []\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        que = [[i, 0] for i in range(numCourses)]\n",
    "        for i in prerequisites:\n",
    "            que[i[0]].append(i[1])\n",
    "            que[i[0]][1] += 1\n",
    "        out = []\n",
    "\n",
    "        while que:\n",
    "            que.sort(key=lambda x:x[1])\n",
    "            res = que.pop(0)\n",
    "            if res[1]:\n",
    "                return []\n",
    "            for i in que:\n",
    "                if res[0] in i[2:]:\n",
    "                    i[1] -= 1\n",
    "            out.append(res[0])\n",
    "\n",
    "\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        ins = [0 for _ in range(numCourses)]\n",
    "        edges = [[] for _ in range(numCourses)]\n",
    "        for t, f in prerequisites:\n",
    "            ins[t] += 1\n",
    "            edges[f].append(t)\n",
    "        ret = []\n",
    "        q = deque()\n",
    "        for i in range(numCourses):\n",
    "            if ins[i] == 0:\n",
    "                q.append(i)\n",
    "        while len(q):\n",
    "            i = q.popleft()\n",
    "            ret.append(i)\n",
    "            for t in edges[i]:\n",
    "                ins[t] -= 1\n",
    "                if ins[t] == 0:\n",
    "                    q.append(t)\n",
    "        return ret if len(ret) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        edges=[[] for _ in range(numCourses)]\n",
    "        indegree=[0]*numCourses\n",
    "        for k,v in prerequisites:\n",
    "            edges[v].append(k)\n",
    "            indegree[k]+=1\n",
    "        q=deque()\n",
    "        for i in range(numCourses):\n",
    "            if indegree[i]==0:\n",
    "                q.append(i)\n",
    "        ans=[]\n",
    "        while q:\n",
    "            cur=q.popleft()\n",
    "            ans.append(cur)\n",
    "            for node in edges[cur]:\n",
    "                indegree[node]-=1\n",
    "                if indegree[node]==0:\n",
    "                    q.append(node)\n",
    "        return ans if len(ans)==numCourses else []\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        edges = {}\n",
    "        indegree = [0]*numCourses\n",
    "        res = []\n",
    "        for p in prerequisites:\n",
    "            indegree[p[0]]+=1\n",
    "            if p[1] in edges:\n",
    "                edges[p[1]].append(p[0])\n",
    "            else:\n",
    "                edges[p[1]] = [p[0]]\n",
    "        q = deque()\n",
    "        for i,v in enumerate(indegree):\n",
    "            if v == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            temp = q.popleft()\n",
    "            indegree[temp] -=1\n",
    "            res.append(temp)\n",
    "            if temp in edges:\n",
    "                for j in edges[temp]:\n",
    "                    indegree[j] -=1\n",
    "                    if indegree[j] == 0:\n",
    "                        q.append(j)\n",
    "        if len(res) == numCourses:\n",
    "            return res\n",
    "        else:return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = self.build_graph(numCourses, prerequisites)\n",
    "\n",
    "        indegree = [0] * numCourses\n",
    "        for edge in prerequisites:\n",
    "            indegree[edge[0]] += 1\n",
    "\n",
    "        q = deque()\n",
    "        for i in range(numCourses):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        res = [0] * numCourses\n",
    "\n",
    "        count = 0\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            res[count] = cur\n",
    "            count += 1\n",
    "            for next_ in graph[cur]:\n",
    "                indegree[next_] -= 1\n",
    "                if indegree[next_] == 0:\n",
    "                    q.append(next_)\n",
    "\n",
    "        if count != numCourses:\n",
    "            return []\n",
    "\n",
    "        return res\n",
    "\n",
    "    def build_graph(self, numCourses: int, prerequisites: List[List[int]]):\n",
    "        graph = {node: set() for node in range(numCourses)}\n",
    "        for edge in prerequisites:\n",
    "            from_, to_ = edge[1], edge[0]\n",
    "            graph[from_].add(to_)\n",
    "        return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        edges = [[] for _ in range(numCourses)]\n",
    "        inds = [0]*numCourses\n",
    "        for p in prerequisites:\n",
    "            inds[p[0]] += 1\n",
    "            edges[p[1]].append(p[0])\n",
    "        que = collections.deque()\n",
    "        for i in range(numCourses):\n",
    "            if inds[i]==0:\n",
    "                que.append(i)\n",
    "        path = []\n",
    "        while len(que)>0:\n",
    "            top = que.popleft()\n",
    "            path.append(top)\n",
    "            for edge in edges[top]:\n",
    "                inds[edge] -= 1\n",
    "                if inds[edge]==0:\n",
    "                    que.append(edge)\n",
    "        if len(path)<numCourses:\n",
    "            return []\n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        indegree = [0] * numCourses\n",
    "        for prerequisite in prerequisites:\n",
    "            indegree[prerequisite[0]] += 1\n",
    "        q = deque()\n",
    "        for i in range(len(indegree)):\n",
    "            if indegree[i] == 0:\n",
    "                q.appendleft(i)\n",
    "        path = []\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            if cur not in path:\n",
    "                path.append(cur)\n",
    "            for prerequisite in prerequisites:\n",
    "                if cur == prerequisite[1]:\n",
    "                    indegree[prerequisite[0]] -= 1\n",
    "                    if indegree[prerequisite[0]] == 0:\n",
    "                        q.appendleft(prerequisite[0])\n",
    "        return path if len(path) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = collections.defaultdict(list) # val is neighbors\n",
    "        indeg = [0]*numCourses\n",
    "        # Build Graph\n",
    "        for prereq in prerequisites:\n",
    "            graph[prereq[1]].append(prereq[0])\n",
    "            indeg[prereq[0]] += 1\n",
    "        \n",
    "        bfs = deque([i for i in range(numCourses) if indeg[i] == 0])\n",
    "        courses = list(bfs)\n",
    "        while bfs:\n",
    "            course = bfs[0]\n",
    "            bfs.popleft()\n",
    "            for neighbor in graph[course]:\n",
    "                indeg[neighbor] -= 1\n",
    "                if not indeg[neighbor]:\n",
    "                    bfs.append(neighbor)\n",
    "                    courses.append(neighbor)\n",
    "\n",
    "        return courses if len(courses) >= numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        def build_graph(prerequisites):\n",
    "            graph = [[] for _ in range(numCourses)]\n",
    "            for _to, _from in prerequisites:\n",
    "                graph[_from].append(_to)\n",
    "            return graph\n",
    "\n",
    "        n = len(prerequisites)\n",
    "        graph = build_graph(prerequisites)\n",
    "        integer = [0 for _ in range(numCourses)]\n",
    "        for _to in graph:\n",
    "            for i in _to:\n",
    "                integer[i] += 1\n",
    "\n",
    "        queue = []\n",
    "        for j,edge in enumerate(integer):\n",
    "            if edge == 0:\n",
    "                queue.append(j)\n",
    "        print(graph)\n",
    "        print(integer)\n",
    "        cnt = 0\n",
    "        ans = []\n",
    "        print(\"q\",queue)\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            cnt += 1\n",
    "            ans.append(node)\n",
    "            for _to in graph[node]:\n",
    "                integer[_to] -= 1\n",
    "                if integer[_to] == 0:\n",
    "                    queue.append(_to)\n",
    "\n",
    "        if cnt == numCourses:\n",
    "            return ans\n",
    "        else:\n",
    "            return []\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        edges=defaultdict(set)\n",
    "        parents=defaultdict(list)\n",
    "        cnt=[0]*numCourses\n",
    "        for u,v in prerequisites:\n",
    "            edges[u].add(v)\n",
    "            parents[v].append(u)\n",
    "            cnt[u]=-1\n",
    "        ans=[]\n",
    "        q=deque([u for u in range(numCourses) if cnt[u]==0])\n",
    "        while q:\n",
    "            ans.append(q[0])\n",
    "            v=q.popleft()\n",
    "            for u in parents[v]:\n",
    "                edges[u].remove(v)\n",
    "                if len(edges[u])==0:\n",
    "                    q.append(u)\n",
    "        return ans if len(ans)==numCourses else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        in_degree = {i: set() for i in range(numCourses)}\n",
    "        out_degree = {i: set() for i in range(numCourses)}\n",
    "        for p0,p1 in prerequisites:\n",
    "            in_degree[p0].add(p1)\n",
    "            out_degree[p1].add(p0)\n",
    "        keys = [k for k in in_degree.keys() if not in_degree[k]]\n",
    "        while keys:\n",
    "            for _ in range(len(keys)):\n",
    "                k = keys.pop()\n",
    "                res.append(k)\n",
    "                for j in out_degree.pop(k):\n",
    "                    in_degree[j].remove(k)\n",
    "                    if not in_degree[j]:\n",
    "                        keys.append(j)\n",
    "        return [] if out_degree else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        in_degree = {i: set() for i in range(numCourses)}\n",
    "        out_degree = {i: set() for i in range(numCourses)}\n",
    "        for p0,p1 in prerequisites:\n",
    "            in_degree[p0].add(p1)\n",
    "            out_degree[p1].add(p0)\n",
    "        keys = [k for k in in_degree.keys() if not in_degree[k]]\n",
    "        while keys:\n",
    "            for _ in range(len(keys)):\n",
    "                k = keys.pop()\n",
    "                res.append(k)\n",
    "                for j in out_degree.pop(k):\n",
    "                    in_degree[j].remove(k)\n",
    "                    if not in_degree[j]:\n",
    "                        keys.append(j)\n",
    "        return [] if out_degree else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, neighbors=None):\n",
    "        self.val = val\n",
    "        self.in_degree = 0  # 入度\n",
    "        self.neighbors = neighbors if neighbors is not None else set()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        if len(prerequisites) == 0:\n",
    "            return list(range(numCourses))\n",
    "\n",
    "        nodes = {}  # 所有节点\n",
    "        zero_in_degree = {}  # 入度为0的节点\n",
    "        for course in range(numCourses):\n",
    "            nodes[course] = Node(course)  # 初始化节点\n",
    "            zero_in_degree[course] = None  # 初始认为所有节点的入度统计都为0\n",
    "\n",
    "        for prerequisite in prerequisites:\n",
    "            parent_node = nodes[prerequisite[1]]\n",
    "            child_node = nodes[prerequisite[0]]\n",
    "            child_node.in_degree += 1  # 子节点入度增加\n",
    "            if prerequisite[0] in zero_in_degree:\n",
    "                zero_in_degree.pop(prerequisite[0])  # 入度不为0的节点删除\n",
    "            parent_node.neighbors.add(child_node)  # 初始化邻居\n",
    "\n",
    "        node_deque = deque()\n",
    "        node_deque.extend(zero_in_degree.keys())  # 所有入度为0的入队\n",
    "        result = []\n",
    "        while len(node_deque) != 0:\n",
    "            node_key = node_deque.popleft()\n",
    "            node = nodes[node_key]\n",
    "            result.append(node.val)  # 入度为0已处理的可以放入拓扑排序的结果\n",
    "            for neighbor in node.neighbors:\n",
    "                neighbor.in_degree -= 1  # 去掉父节点后，子节点的入度减少\n",
    "                if neighbor.in_degree == 0:\n",
    "                    node_deque.append(neighbor.val)  # 入度为0的子节点入队\n",
    "\n",
    "        if len(result) == numCourses:  # 拓扑排序的结果集和课程数量相等\n",
    "            return result\n",
    "\n",
    "        return []  # 拓扑排序完成，还有入度不为0的节点，则存在环路"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,val):\n",
    "        self.val = val\n",
    "        self.aft = []\n",
    "        self.pre = []\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.course = dict()\n",
    "    def findOrder(self, numCourses: int, prerequisites) -> bool:\n",
    "        nums = []\n",
    "        for i in prerequisites:\n",
    "            a,b = i[0],i[1]\n",
    "            if a not in self.course:\n",
    "                self.course[a] = Node(a)\n",
    "            if b not in self.course:\n",
    "                self.course[b] = Node(b)\n",
    "            self.course[a].pre.append(self.course[b])\n",
    "            self.course[b].aft.append(self.course[a])\n",
    "        for i in self.course:\n",
    "            if not self.course[i].pre:\n",
    "                learned = [self.course[i]]\n",
    "                while learned:\n",
    "                    temp = []\n",
    "                    for j in learned:\n",
    "                        if j.val != \"Q\":\n",
    "                            nums.append(j.val)\n",
    "                            j.val = \"Q\"\n",
    "                            for p in j.aft:\n",
    "                                flag = True\n",
    "                                for k in p.pre:\n",
    "                                    \n",
    "                                    if k.val != \"Q\":\n",
    "                                        flag = False\n",
    "                                        break\n",
    "                                if flag:\n",
    "                                    temp.append(p)\n",
    "                    learned = temp\n",
    "        if len(nums) == len(self.course):\n",
    "            res = []\n",
    "            for i in range(numCourses):\n",
    "                if i not in nums:\n",
    "                    res.append(i)\n",
    "            return res+nums\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        self.postorder = []\n",
    "        self.hasCycle = False\n",
    "        self.visited = [False]*numCourses\n",
    "        self.onPath = [False]*numCourses\n",
    "        graph = self.buildGraph(numCourses,prerequisites)\n",
    "        for i in range(numCourses):\n",
    "            self.traverse(graph,i)\n",
    "        if self.hasCycle:\n",
    "            return []\n",
    "        return self.postorder[::-1]\n",
    "\n",
    "    def traverse(self,graph,s):\n",
    "        if self.onPath[s]:\n",
    "            self.hasCycle = True\n",
    "        if self.hasCycle or self.visited[s]:\n",
    "            return\n",
    "        self.onPath[s] = True\n",
    "        self.visited[s] = True\n",
    "        for t in graph[s]:\n",
    "            self.traverse(graph,t)\n",
    "        self.postorder.append(s)\n",
    "        self.onPath[s] = False\n",
    "\n",
    "\n",
    "    def buildGraph(self,numCourses,prerequisites):\n",
    "        graph = [[] for _ in range(numCourses)] \n",
    "        for edge in prerequisites:\n",
    "            fromNode = edge[1]\n",
    "            toNode = edge[0]\n",
    "            graph[fromNode].append(toNode)\n",
    "        return graph\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        def is_circle(course: int) -> bool:\n",
    "            if visited[course]: return visited[course] == 2  # 值为1，回到正在搜索的节点，有环；值为2，遇到一个处理过的节点，这个节点的后续路径是无环的，无需再搜索。 \n",
    "            visited[course] = 1    # 标记当前节点正在搜索\n",
    "            for next_course in p[course]:\n",
    "                if not is_circle(next_course): return False  # 处理当前节点的所有下一个连接节点\n",
    "            visited[course] = 2    # 该节点后续路径无环，比较为处理过\n",
    "            res[self.idx] = course    # DFS一定是将最后的节点先处理完毕，将处理完毕的节点加入结果表中\n",
    "            self.idx -= 1\n",
    "            return True\n",
    "\n",
    "        p =  [[] for _ in range(numCourses)] # 图连接矩阵\n",
    "        res = [i for i in range(numCourses)]   # 初始学习顺序表，每个位置存放一个课程\n",
    "        self.idx = numCourses - 1    # 表索引，表示课程要添加的位置; 课程倒序添加\n",
    "        # 根据先修课程关系生成图连接矩阵\n",
    "        for (a, b) in prerequisites:\n",
    "            p[b].append(a)\n",
    "        # 枚举每一个节点为起点的路径进行dfs\n",
    "        visited = [0] * numCourses\n",
    "        for i in range(numCourses):\n",
    "            if not visited[i] and not is_circle(i): return [] # 节点未访问过，说明是一条路径的起点，搜索该路径是否存在环\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = collections.defaultdict(list) # val is neighbors\n",
    "        visit_status = [0] * numCourses # 0: not searched; 1: searching; 2: finished\n",
    "        stk = []\n",
    "        # Build Graph\n",
    "        for prereq in prerequisites:\n",
    "            graph[prereq[1]].append(prereq[0])\n",
    "        \n",
    "        def dfs(course):\n",
    "            if visit_status[course] == 2: return True\n",
    "            elif visit_status[course] == 1: return False\n",
    "\n",
    "            visit_status[course] = 1\n",
    "            for neighbor in graph[course]:\n",
    "                if not dfs(neighbor): return False\n",
    "            visit_status[course] = 2\n",
    "            stk.append(course)\n",
    "            return True\n",
    "\n",
    "        for course in range(numCourses):\n",
    "            if not visit_status[course]: \n",
    "                if not dfs(course): return []\n",
    "        return stk[::-1] # reverse"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
